﻿using System.Text;

namespace DataStructure;

public class CirLinkList<E> : IList<E>
{
    //私有的内部结点类
    private class Node
    {
        public E e; //结点中存储的元素
        public Node next; //存储下一个结点的引用

        //通过元素和下一个结点的引用创建结点
        public Node(E e, Node next)
        {
            this.e = e;
            this.next = next;
        }

        //通过元素创建结点
        public Node(E e) : this(e, null)
        {
        }

        //输出结点的信息
        public override string ToString()
        {
            return e.ToString();
        }
    }

    //头指针标识链表的头部
    private Node head;

    //尾指针标记链表尾部结点
    private Node tail; //*

    //链表中元素的个数
    private int N;

    //链表初始化：一个结点也没有，head指向空，N为0
    public CirLinkList()
    {
        head = null;
        tail = null; //*
        N = 0;
    }

    //只读属性：获取链表中元素的个数
    public int Count { get { return N; } }

    //只读属性：判断链表是否为空
    public bool IsEmpty { get { return head == null || tail == null || N == 0; } }

    //私有的辅助函数，通过索引查找对应的结点
    //有了它作为前提，能更方便的实现增删改查相应的功能
    private Node GetByIndex(int index)
    {
        if (index < 0 || index >= N)
        {
            throw new ArgumentOutOfRangeException(nameof(index), "索引超出范围");
        }

        Node cur = head;
        for (int i = 0; i < index; i++)
        {
            cur = cur.next;
        }

        return cur;
    }

    //添加索引器，对索引的元素进行读写，，索引从0开始。
    public E this[int index]
    {
        //获取指定位置的元素值
        get { return GetByIndex(index).e; }

        //修改指定位置的元素值
        set { GetByIndex(index).e = value; }
    }

    //获取或设置数组头部的元素值
    public E First
    {
        get { return this[0]; }

        set { this[0] = value; }
    }

    //获取或设置数组尾部的元素值
    public E Last
    {
        get { return this[N - 1]; }

        set { this[N - 1] = value; }
    }

    //往链表添加元素
    public void Add(int index, E e)
    {
        if (index == 0) //头插
        {
            //Node node=new Node(e);
            //node.next = head;
            //head = node;
            
            head = new Node(e, head);

            if (N==0) //*，考虑空表情形，此时tail还为null
            {
                tail = head;
            }

            tail.next = head; //*
        }
        else //中插或尾插
        {
            Node pre = GetByIndex(index - 1);

            Node node = new Node(e);
            node.next = pre.next;
            pre.next = node;

            //pre.next = new Node(e, pre.next);

            if (index == N) //*，如果尾插，还要处理一下
            {
                tail = node;
                tail.next = head;
            }
        }

        N++;
    }

    //在链表的头部添加元素
    public void AddFirst(E e)
    {
        Add(0, e);
    }

    //在链表的尾部添加元素
    public void AddLast(E e)
    {
        Add(N, e);
    }

    //查询链表中元素e的位置索引
    public int IndexOf(E e)
    {
        Node cur = head;
        int index = 0;
        while (cur != null)
        {
            if (cur.e.Equals(e))
            {
                return index;
            }

            cur = cur.next;
            index++;
        }

        return -1;
    }

    //查询链表中是否包含元素e
    public bool Contains(E e)
    {
        return IndexOf(e) >= 0;
    }

    //删除链表第index位置的元素（从0开始计算）
    public E RemoveAt(int index)
    {
        if (index == 0)
        {
            Node delNode = head;

            head = head.next;
            tail.next = head; //*

            N--;
            if (N==0)
            {
                head = tail = null;
            }

            return delNode.e;
        }
        else
        {
            Node pre = GetByIndex(index - 1);

            Node delNode = pre.next;

            if (delNode == null)
            {
                throw new ArgumentOutOfRangeException(nameof(index), "索引超出范围");
            }

            pre.next = delNode.next;

            if (index == N - 1) //*，如果删除的是尾结点，还要处理下
            {
                tail = pre;
                tail.next = head;
            }

            N--;
            if (N == 0)
            {
                head = tail = null;
            }

            return delNode.e;
        }


    }

    //删除链表的头部元素
    public E RemoveFirst()
    {
        return RemoveAt(0);
    }

    //删除链表的尾部元素
    public E RemoveLast()
    {
        return RemoveAt(N - 1);
    }

    //删除链表指定的元素e
    public bool Remove(E e)
    {
        int index = IndexOf(e);

        //链表空，删除失败，返回假。
        if (head == null)
        {
            return false;
        }

        //链表不空且删除的是头节点
        if (head.e.Equals(e))
        {
            head = head.next;
            tail.next = head; //*

            N--;
            if (N == 0)
            {
                head = tail = null;
            }

            return true;
        }

        //链表不空且删除的不是头节点
        Node pre = head; //pre为当前要删除的节点的前一节点，从head开始移动。
        while (pre.next != null) //pre.next为当前节点，从第二个节点开始一直遍历到最后节点。
        {
            if (pre.next.e.Equals(e))
            {
                break;
            }

            pre = pre.next;
        }

        //元素不存在，删除失败，返回假。
        if (pre.next == null)
        {
            return false;
        }

        //找到元素所在的节点，成功删除该节点，返回真。
        pre.next = pre.next.next;

        if (index == N - 1) //如果删除的是尾结点，还要处理下
        {
            tail = pre;
            tail.next = head;
        }

        N--;
        if (N==0)
        {
            head = tail = null;
        }

        return true;
    }

    //清空单链表
    public void Clear()
    {
        head = null;
        tail = null;
        N = 0;
    }

    //打印链表
    public override string ToString()
    {
        if (IsEmpty)
        {
            return String.Empty;
        }

        StringBuilder res = new StringBuilder();
        Node cur = head;
        while (cur != tail)
        {
            res.Append(cur + "->");//cur.ToString()
            cur = cur.next;
        }
        res.Append(tail + "->" + head);
        return res.ToString();
    }    
}

class CirLinkList
{
    static void Main(string[] args)
    {
        CirLinkList<int> cl = new();
        cl.AddLast(1);
        cl.AddLast(2);
        cl.AddLast(3);
        cl.AddFirst(0);
        cl.Remove(0);
        cl.Remove(3);
        cl.Remove(1);
        cl.Remove(2);
        Console.WriteLine(cl);
    }
}
